#include <vector>
#include <iostream>

using namespace std;

// Space: O(1) 
// Time:  O(n^2)
vector<int> bubbleSort(vector<int> array) {
  //              vEnd
  // [1, 2, 3, 8, 9]
  //  ^i
  
  int end = array.size() - 1;
  bool sorted = false;
  // n
  // n + (n - 1) + (n - 2) + ... + 1 = n (n + 1) / 2 = n^2
  // n = 100 n/2 = 50 n^2/2 = 5000
  // n = 100000000000000
  while (!sorted) {
    sorted = true;

    for (int i = 0; i < end; ++i) {
      if (array[i] > array[i + 1]) {
        swap(array[i], array[i + 1]);
        sorted = false;
      }
    }

    --end;
  }

  return array;
}


void bubbleSort1(vector<int> array, int lastPos) {
  if (lastPos == 0) {
    return;
  }

  // 交换检查 0 到 lastPos 之间所有的元素
  
  return bubbleSort1(array, lastPos - 1);
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> array {1, 2, 3, 4, 5};
  bubbleSort1(array, array.size() - 1);
  return 0;
}
